package oop.ex4.crosswords.strategies;

import java.io.IOException;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.HashSet;
import java.util.Iterator;
import java.util.Set;
import java.util.SortedSet;
import java.util.TreeSet;

import oop.ex4.crosswords.CrosswordDictionary;
import oop.ex4.crosswords.CrosswordEntry;
import oop.ex4.crosswords.CrosswordPosition;
import oop.ex4.crosswords.EntriesComparator;
import oop.ex4.crosswords.MyCrossword;
import oop.ex4.crosswords.MyCrosswordDictionary;
import oop.ex4.crosswords.MyCrosswordEntry;
import oop.ex4.crosswords.MyCrossword.CrosswordSquare;

/**
 * The small dictionary strategy. <br>
 * In the case when there are more entries then terms then does a terms based search.
 * @author yomach
 * @author mbattat
 */
public class SmallDictionaryCrosswordStrategy extends CrosswordStrategy {

	///////////////////////////////////////////////////////
	////////////////////////Constants//////////////////////
	///////////////////////////////////////////////////////

	/**
	 * The strategy's rating.
	 */
	private static final int STRATEGY_RATING = 5;

	///////////////////////////////////////////////////////
	//////////////////////Data Members/////////////////////
	///////////////////////////////////////////////////////

	/**
	 * The dictionary.
	 */
	protected LengthBasedExtendedCrosswordDictionary _dict;

	///////////////////////////////////////////////////////
	//////////////////////Constructors/////////////////////
	///////////////////////////////////////////////////////

	/** 
	 * A constructor that sets the board to the SmallDictionary strategy.
	 * @param board The board.
	 * @param dict The dictionary.
	 */
	public SmallDictionaryCrosswordStrategy() {
		super();
	}

	///////////////////////////////////////////////////////
	/////////////////////Public Methods////////////////////
	///////////////////////////////////////////////////////

	@Override
	public void initializeStrategy(CrosswordDictionary dict, CrosswordSquare[][] board) {
		super.initializeStrategy(dict, board);		
		int termSum = 0;
		int longstEntryLength = _entriesList.longestEntryLength();
		for (String term : _dict.getTerms()) {
			if (term.length() <= longstEntryLength) { 
				termSum += term.length(); 
			}
			else { _dict.markAsUsed(term); }
		}
		_bestQuality = _qualityBound = termSum;

		int shortestEntryLength = _entriesList.shortestEntryLength();
		for (int i = shortestEntryLength; i <= longstEntryLength; i++) {
			Iterator<CrosswordEntry> iterator = _entriesList.getIterator(i);
			while (iterator.hasNext()) {
				CrosswordEntry entry = iterator.next();
				if (_entriesList.getEntryLength(entry) < _dict.shortestWordLength()) { // For each entry that we can fit a word into.
					iterator.remove();
				}
			}
		}
	}

	@Override
	public void doMove(CrosswordEntry move) {
		super.doMove(move);
		calculateQualityBound();
	}

	@Override
	public void undoMove(CrosswordEntry move) {
		super.undoMove(move);
		calculateQualityBound();
	}

	@Override
	public Iterator<CrosswordEntry> getMoveIterator() {
		return new SmallDictionaryMovesIterator();
	}

	@Override
	public int isGoodStrategy(CrosswordDictionary dict,
			CrosswordSquare[][] board) {
		_dict = new LengthBasedExtendedCrosswordDictionary(dict);
		super._dict = _dict;
		if (getValidTermNum(board) < getValidEntryNum(board)) { return STRATEGY_RATING; }
		return 0;
	}

	///////////////////////////////////////////////////////
	////////////////////Private Methods////////////////////
	///////////////////////////////////////////////////////

	/**
	 * Calculate the quality bound by iterating over the entire list of unused words
	 * & checking which can still fit into board.
	 */
	private void calculateQualityBound() {
		int wordSum = 0;
		int longstEntryLength = _entriesList.longestEntryLength();
		for (int i = _dict.shortestWordLength(); i <= _dict.longestWordLength(); i++) {
			for (String term : _dict.findMatchingWords(i)) {
				if (_dict.getUsedTermsList(term.length()).contains(term)) { continue; }
				if (term.length() <= longstEntryLength) {
					boolean found = false;
					for (int j = longstEntryLength; j >= term.length() && !found; j--) {
						for (CrosswordEntry entry : _entriesList.getSet(j)) {
							CrosswordPosition pos = entry.getPosition();
							// Checks if the word can fit into an entry.
							if (MyCrossword.CrosswordSquare.overlappingAmount(_board[pos.getX()][pos.getY()].getCharsAround(pos.isVertical()), term) > -1) { 
								wordSum += term.length();
								found = true;
								break;
							}
						}
					}
				}
			}
		}
		_qualityBound = _quality + wordSum;
	}

	/**
	 * A nested decorator dictionary class that implements the ExtendedCrosswordDictionary.
	 * It's meant to be used with other simple dictionary implementation. <br>
	 * This class supports finding of words that match a given length in O(1). 
	 * @author yomach
	 * @author mbattat
	 */
	private class LengthBasedExtendedCrosswordDictionary implements ExtendedCrosswordDictionary {

		///////////////////////////////////////////////////////
		//////////////////////Data Members/////////////////////
		///////////////////////////////////////////////////////

		/**
		 * A basic implementation of a dictionary.
		 */
		protected CrosswordDictionary _simpleDictionary;

		/**
		 * The extended dictionary.
		 */
		protected ArrayList<SortedSet<String>> _extendedDictionary;

		/**
		 * A set that holds all of the used terms.
		 */
		protected ArrayList<HashSet<String>> _usedTerms;

		///////////////////////////////////////////////////////
		//////////////////////Constructors/////////////////////
		///////////////////////////////////////////////////////

		/**
		 * Constructs a new dictionary based on a the given dictionary.
		 * @param dictionary The dictionary.
		 */
		public LengthBasedExtendedCrosswordDictionary (CrosswordDictionary dictionary) {
			_simpleDictionary = dictionary;
			createExtendedDictionary();
		}

		///////////////////////////////////////////////////////
		/////////////////////Public Methods////////////////////
		///////////////////////////////////////////////////////

		/**
		 * Returns all the words in the dictionary with the given length. <br>
		 * The words returned will be sorted lexicography. <br>
		 * The set returned is the original one, any changes on it will affect
		 * the dictionary. <br>
		 * Despite that, using the getTerms method will not be affected by the above.
		 * @param length The length of the requested terms.
		 * @return All possible words that fit the length.
		 */
		public SortedSet<String> findMatchingWords(int length) {
			if (invalidLength(length)) { return null; }
			return new TreeSet<String>(_extendedDictionary.get(length-2));
		}

		@Override
		public String getTermDefinition(String term) {
			return _simpleDictionary.getTermDefinition(term);
		}

		@Override
		public Set<String> getTerms() {
			return _simpleDictionary.getTerms();
		}

		@Override
		public void load(String dictFileName) throws IOException {
			_simpleDictionary = new MyCrosswordDictionary(dictFileName); // Creates the simple dictionary.
			createExtendedDictionary();
		}

		@Override
		public boolean markAsUsed(String term) {
			return _simpleDictionary.getTerms().contains(term) ?
					_usedTerms.get(term.length()-2).add(term) :
						false;
		}

		@Override
		public boolean markAsUnused(String term) {
			return _usedTerms.get(term.length()-2).remove(term);
		}

		@Override
		public Set<String> getUsedTermsList(int length) {
			if (invalidLength(length)) { return null; }
			return _usedTerms.get(length-2);
		}

		@Override
		public int longestWordLength() {
			for (int i = _extendedDictionary.size()-1; i >= 0; i--) {
				if (_extendedDictionary.get(i).size() - _usedTerms.get(i).size() > 0) { 
					return i+2;
				}
			}
			return -1; // Dictionary is empty. 
		}

		@Override
		public int shortestWordLength() {
			for (int i = 0; i < _extendedDictionary.size(); i++) {
				if (_extendedDictionary.get(i).size() - _usedTerms.get(i).size() > 0) { return i+2; }
			}
			return 0; // Dictionary is empty. 
		}

		///////////////////////////////////////////////////////
		/////////////////////Private Methods///////////////////
		///////////////////////////////////////////////////////

		/**
		 * Returns true iff the length given is less than 1 or bigger then the size of the list.
		 * @param length The length.
		 * @return true iff the length is outside the bounds.
		 */
		private boolean invalidLength(int length) {
			return (length <= 1 || length > _extendedDictionary.size()+1);
		}

		/**
		 * Creates the extended dictionary.
		 */
		private void createExtendedDictionary() {
			Iterator<String> iterator = _simpleDictionary.getTerms().iterator();
			int maxLength = findLongestWord();
			_usedTerms = new ArrayList<HashSet<String>>(maxLength-1);
			// Creates the extended dictionary database, contains words from length 2+.
			_extendedDictionary = new ArrayList<SortedSet<String>>(maxLength-1); 
			for (int i = 0; i < maxLength-1; i++){
				_extendedDictionary.add(i, new TreeSet<String>());
				_usedTerms.add(i, new HashSet<String>());
			}
			iterator = _simpleDictionary.getTerms().iterator();
			while (iterator.hasNext()){    
				// Adds all the word's in the simple dictionary to
				// The extended dictionary
				String word = iterator.next();
				int length = word.length();
				_extendedDictionary.get(length-2).add(word);
			}	
		}

		/**
		 * Find and returns the length of the longest word in the dictionary by iterating over it.
		 * @return The length of the longest word.
		 */
		private int findLongestWord() {
			int maxLength = 0;
			for (String word : _simpleDictionary.getTerms()){
				if (word.length() > maxLength) { maxLength = word.length();}
			}
			return maxLength;
		}
	}

	/**
	 * A nested Iterator that iterate over all possible moves by the small dictionary strategy.
	 * @author yomach
	 * @author mbattat
	 */
	private class SmallDictionaryMovesIterator extends MovesIterator{

		/**
		 * An Iterator that iterate over the entries in the crossword.
		 */
		private Iterator<CrosswordEntry> _entryIterator;

		/**
		 * An Iterator that iterate over the possible terms.
		 */
		private Iterator<String> _termIterator;

		/**
		 * Holds the next iterations for the small dictionary strategy.
		 */
		private TreeSet<CrosswordEntry> _nextIterations;

		/**
		 * Holds the length of the current term.
		 */
		private int _currentTermLength;

		///////////////////////////////////////////////////////
		//////////////////////Constructors/////////////////////
		///////////////////////////////////////////////////////

		/**
		 * Constructs a new MoveIterator in a certain strategy.
		 */
		public SmallDictionaryMovesIterator() {
			super();
			_nextIterations = new TreeSet<CrosswordEntry>(new SmallDictionaryMovesComparator());
			_currentTermLength = Math.min(_maxFit, _dict.longestWordLength()) + 1;
		}

		///////////////////////////////////////////////////////
		////////////////////Private Methods////////////////////
		///////////////////////////////////////////////////////

		/**
		 * {@inheritDoc} <br>
		 * SmallDictionary strategy - check the terms from longest to shortest.
		 * for every term order the moves in order by:
		 * 1. number of overlapping letters in every entry.
		 * 2. x coordinate, y coordinate, vertical/horizontal.  
		 * @return The next move.
		 */
		@Override
		protected CrosswordEntry createNextMove() {
			if (_nextIterations.isEmpty()) {
				if (_currentTermLength <= _minFit) {
					return null;
				}
				while ((_termIterator == null || !_termIterator.hasNext()) && _currentTermLength > _minFit) {
					_termIterator =  _dict.findMatchingWords(--_currentTermLength).iterator();
				}
				String currentTerm = null;
				while (_termIterator.hasNext()) {
					currentTerm = _termIterator.next();
					if (!_dict.getUsedTermsList(_currentTermLength).contains(currentTerm)) {
						break;
					}
					currentTerm = null;
				}
				if (currentTerm == null) { return createNextMove(); }
				for (int i = _maxFit; i >= _currentTermLength; i--) {
					_entryIterator = _entriesList.getIterator(i);
					CrosswordEntry nextEntry;
					while (_entryIterator.hasNext()) {
						nextEntry = _entryIterator.next();
						if (!_entriesList.getUsedEntriesSet(i).contains(nextEntry)) {
							CrosswordPosition pos = nextEntry.getPosition();
							if (MyCrossword.CrosswordSquare.overlappingAmount(_board[pos.getX()][pos.getY()].getCharsAround(pos.isVertical()), currentTerm) > -1){
								_nextIterations.add(new MyCrosswordEntry(currentTerm, _dict, pos));
							}
						}
					}
				}

				if (_nextIterations.isEmpty()) {
					return createNextMove();
				}
			}
			return _nextIterations.pollFirst();
		}

		/**
		 * A comparator that compares between two moves (CrosswordEntries). <br>
		 * First by the amount of overlapping their word creates with other entries &
		 * then according to the EntriesComparator.
		 * 
		 * @see EntriesComparator
		 * 
		 * @author yomach
		 * @author mbattat
		 */
		private class SmallDictionaryMovesComparator implements Comparator<CrosswordEntry> {
			
            ///////////////////////////////////////////////////////
			/////////////////////Public Methods////////////////////
			///////////////////////////////////////////////////////
			@Override
			public int compare(CrosswordEntry move1, CrosswordEntry move2) {
				CrosswordPosition pos1 = move1.getPosition();
				CrosswordPosition pos2 = move2.getPosition();
				int x1 = pos1.getX();
				int y1 = pos1.getY();
				int x2 = pos2.getX();
				int y2 = pos2.getY();
				int overlapping1 = MyCrossword.CrosswordSquare.overlappingAmount(String.valueOf(_board[x1][y1].getCharsAround(pos1.isVertical())), move1.getTerm());
				int overlapping2 = MyCrossword.CrosswordSquare.overlappingAmount(String.valueOf(_board[x2][y2].getCharsAround(pos2.isVertical())), move2.getTerm());
				if (overlapping1 < overlapping2) { return 1; }
				if (overlapping1 > overlapping2) { return -1; }
				return EntriesComparator.compareEntriesLocation(move1, move2);
			}
		}
	}
}
